package mo.tags.binarysearchtree;

import mo.common.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class L95 {

    public List<TreeNode> generateTrees(int n) {
        return generateTree(1, n);
    }

    private List<TreeNode> generateTree(int start, int end) {
        List<TreeNode> trees = new ArrayList<>();
        if (start > end) {
            trees.add(null);
            return trees;
        }
        for (int i = start; i <= end; i++) {
            List<TreeNode> left = generateTree(start, i-1);
            List<TreeNode> right = generateTree(i+1, end);
            for (TreeNode l : left) {
                for (TreeNode r : right) {
                    TreeNode root = new TreeNode(i);
                    root.left = l;
                    root.right = r;
                    trees.add(root);
                }
            }
        }
        return trees;
    }

}
